package ShortestPath;

import pojo.Edge;
import pojo.Pair;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * <p>
 * 最短路基础算法dijkstra
 * 这里由于笔者常用算法竞赛写法，所以先给出堆优化的dijkstra
 * 初学者可能觉得难懂，但其实自己多实现几次多思考会发现方法并不复杂
 * （后续普通写法也会更新ing...）
 * </p>
 * @author: 没天赋
 * @since 2025-2-28
 */
public class Dijkstra {
    //定义最大点数
    public static final int N = (int) (1e5 + 5);
    //定义边数组,这里*2是因为无向图
    public static Edge[] edges = new Edge[N << 1];
    //存邻接表头
    public static int[] head = new int[N];
    //存点到边的距离
    public static int[] dis = new int[N];
    //记录是否访问
    public static int[] vis = new int[N];
    //点数n，边数m,下标id（记录边数）,入度u，出度v，权值w
    public static int n, m, id, u, v, w;
    public static Scanner sc = new Scanner(System.in);
    //定义对组，最小堆按边排序所以first存边权，second存结点号
    //最小堆（堆优化的核心）
    public static PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(p -> p.first));

    /**
     * 主函数功能：
     * dijkstra本就是处理一对多的最短路，也是算法比赛最常用的图论算法之一，更是408考试算法
     * 所以希望大家好好学习本算法
     * 本方法演示dijkstra从1结点到n结点的最短路
     * 但其实本方法求任意一个节点到其它节点都能实现
     *
     * @param args
     */
    public static void main(String[] args) {
        n = sin();
        m = sin();
        for (int i = 0; i < m; i++) {
            u = sin();
            v = sin();
            w = sin();
            //无向图所以双边都要建立（这就是为什么边数组要开双倍N<<1）
            add(u, v, w);
            add(v, u, w);
        }
        System.out.println(dijkstra());
    }

    /**
     * dijkstra算法本体
     */
    public static int dijkstra() {
        //初始化1到各点的距离为最大值
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[1] = 0;

        //初始先把结点1放入堆中，dijkstra就是一种从1个点开始的贪心+bfs算法
        queue.add(new Pair<>(dis[1], 1));
        while (!queue.isEmpty()) {

            //从最小堆中弹出最小节点
            Pair<Integer, Integer> temp = queue.poll();
            if (vis[temp.second] != 0) continue;
            vis[temp.second] = 1;

            //再从这个点开始将其临边都赋值
            for (int i = head[temp.second]; i != 0; i = edges[i].next) {
                int x = edges[i].to;
                if (dis[x] > temp.first + edges[i].val) {
                    dis[x] = temp.first + edges[i].val;
                    // 我有一个朋友之前问我这里想要不要判断访问呢
                    // 其实这里是否判断已访问都可以
                    queue.add(new Pair<>(dis[x], x));
                }
            }
        }
        return dis[n];
    }

    /**
     * 增边
     *
     * @param x
     * @param y
     * @param z
     */
    public static void add(int x, int y, int z) {
        id++;
        edges[id] = new Edge(y, head[x], z);
        head[x] = id;
    }

    /**
     * 读取整数方法
     *
     * @return
     */
    public static int sin() {
        return sc.nextInt();
    }
}

/*
* 测试数据：
* 7 9
1 2 1
1 3 3
2 4 1
3 4 5
2 6 3
4 5 2
6 5 1
4 7 6
5 7 1
* 结果：
* 5
* */